/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[]}
 */
/* 递归 */
var postorder = function (root) {
	const res = []
	helper(root, res)
	return res
}
const helper = (root, res) => {
	if (root == null) return
	for (const ch of root.children) {
		helper(ch, res)
	}
	res.push(root.val)
}
/* 迭代 */
var postorder = function (root) {
	const res = []
	if (root == null) return res
	const map = new Map()
	const stack = []
	let node = root
	while (stack.length || node) {
		while (node) {
			stack.push(node)
			if (!node.children) break
			map.set(node, 0)
			node = node.children[0]
		}
		node = stack[stack.length - 1]
		const index = (map.get(node) || 0) + 1
		const children = node.children
		if (children && children.length > index) {
			map.set(node, index)
			node = children[index]
		} else {
			res.push(node.val)
			stack.pop()
			map.delete(node)
			node = null
		}
	}
	return res
}
/* 迭代优化 */
var postorder = function (root) {
	const res = []
	if (root == null) return
	const stack = [root]
	const visited = new Set()
	while (stack.length) {
		const node = stack[stack.length - 1]
		const children = node.children
		// 如果当前节点位叶子节点或者当前节点已经遍历过
		if (!children.length || visited.has(node)) {
			stack.pop()
			res.push(node.val)
			continue
		}
		for (let i = children.length - 1; i >= 0; i--) {
			stack.push(children[i])
		}
		visited.add(node)
	}
}
